//https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/564726681/

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        auto canShip = [&](int capacity) {
            int sum = 0, requiredDays = 1;
            for (int w : weights) {
                if (sum + w > capacity) {
                    requiredDays++;
                    sum = w;
                    if (requiredDays > days) return false;
                } else {
                    sum += w;
                }
            }
            return true;
        };

        int l = *max_element(weights.begin(), weights.end());
        int r = (1e4)*5*500;
        int ans = r;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (canShip(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};
